package com.chj.chuji.tijie14;

import java.util.ArrayList;

//https://blog.csdn.net/qq_41117236/article/details/87023967
public class Selected02 {
	public static class Node {
		int val;
		Node left;
		Node right;

		public Node(int val) {
			this.val = val;
		}
	}

	public static void posOrderRecur(Node head, ArrayList<Integer> arr) {
		if (head == null) {
			return;
		}

		posOrderRecur(head.left, arr);
		posOrderRecur(head.right, arr);
		arr.add(head.val);
	}

	public static int upper_bound(int l, int r, int x, int[] a) {
		while (l < r) {
			int mid = (l + r) / 2;
			if (a[mid] > x) {
				r = mid;
			} else {
				l = mid + 1;
			}
		}
		return l;
	}

	public static int lower_bound(int l, int r, int x, int[] a) {
		while (l < r) {
			int mid = (l + r) / 2;
			if (a[mid] >= x) {
				r = mid;
			} else {
				l = mid + 1;
			}
		}
		return l;
	}

	public static void main(String[] args) {

		int maxn = 6;
		int n = 5;
		int[] ar = new int[maxn];
		int[] dp = new int[maxn];

		Node n1 = new Node(1);
		Node n2 = new Node(5);
		Node n3 = new Node(4);
		Node n4 = new Node(2);
		Node n5 = new Node(3);

		n1.left = n3;
		n1.right = n2;
		n2.left = n4;
		n2.right = n5;
		ArrayList<Integer> arr02 = new ArrayList<Integer>();

		posOrderRecur(n1, arr02);
		int an = arr02.size();
		for (int i = 1; i <= an; i++) {
			ar[an - i + 1] = arr02.get(i - 1);
		}

		int cnt = 1;
		dp[1] = ar[1];
		for (int i = 2; i <= n; ++i) {
			if (ar[i] > dp[cnt])
				dp[++cnt] = ar[i];
			else {
//				int pos=lower_bound(f+1,f+cnt+1,q[i])-f;
				int pos = lower_bound(1, cnt + 1, ar[i], dp);
				dp[pos] = ar[i];
			}
		}

		System.out.println(cnt);
	}
}

//#include <bits/stdc++.h>
//using namespace std;
//const int maxn=100005;
//int w[maxn],lson[maxn],rson[maxn];
//int q[maxn],f[maxn];
//int tot;
//void dfs(int u)
//{
//	if(!u) return;
//	q[++tot]=u;
//	dfs(rson[u]);
//	dfs(lson[u]);
//}
//int main()
//{
//	int n; scanf("%d",&n);
//	for(int i=1;i<=n;++i) scanf("%d",&w[i]);
//	for(int i=1;i<=n;++i) scanf("%d%d",&lson[i],&rson[i]);
//	dfs(1); //求dfs序
//	for(int i=1;i<=n;++i) q[i]=w[q[i]];
//	int cnt=1;
//	f[1]=q[1];
//	for(int i=2;i<=n;++i)
//    {
//		if(q[i]>f[cnt]) f[++cnt]=q[i];
//		else
//		{
//			int pos=lower_bound(f+1,f+cnt+1,q[i])-f;
//			f[pos]=q[i];
//		}
//	}
//	printf("%d",cnt);
//	return 0;
//}
